package 蓝桥杯算法;

import 二叉树.TreeNode;

import java.util.List;

public class day26 {
    public static void main(String[] args) {
        day26 a=new day26();
        System.out.println(a.findmin(12));
        int[] value={1,2,3,1};
        int[] value2={2,3,2};
        System.out.println(a.maxmoney(value));
        System.out.println(a.Maxmoney(value2));

    }
    public int combine(int[] num,int target){//完全背包问题
        int[] dp=new int[target+1];
        dp[0]=1;
        for(int i=1;i<=target;i++){
            for(int j=1;j<=num.length;j++){
              if(i>=num[j]){
                  dp[i]+=dp[i-num[j]];
              }
            }
        }
        return dp[target];
    }
    public int findmin(int target){
        int[] dp=new int[target+1];
        dp[0]=0;
        int max=Integer.MAX_VALUE;
        for(int i=1;i<=target;i++){
            dp[i]=max;
        }
        for(int j=1;j<=target;j++){
            for(int i=1;i*i<=j;i++){//选择的条件
               dp[j]=Math.min(dp[j],(dp[j-i*i]+1));
            }
        }
        return dp[target];

    }
    public boolean workbank(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (String str : wordDict) {//跳出第一个循环
                int len = str.length();
                //一个接一个的遍历,确保不错过
                if (i >= len && dp[i - len] && str.equals(s.substring(i - len, i))) ;
                {
                    dp[i] = true;
                    break;
                }
            }

        }
        return dp[s.length()];
    }
    public int baggweight(int[] weight,int[]num,int[] value,int target){
        //属于零一背包多加了一个数目限制
        int[] dp=new int[target+1];
        for(int i=0;i<weight.length;i++){
            for(int j=target;j>=weight[i];j--){
                for(int k=0;k<=num[i]&&(j-k*weight[i]>=0);k++){
                    dp[j]=Math.max(dp[j],dp[j-k*weight[i]]+k*value[i]);
                }
            }
        }
        return dp[target];
    }
    public int maxmoney(int[] value){
        int min=Integer.MIN_VALUE;
        int[]dp=new int[value.length];
        for(int i=0;i<value.length;i++){
            dp[i]=min;
        }

        dp[0]=value[0];
        dp[1]=Math.max(dp[0],value[1]);
        for(int i=2;i<value.length;i++){
            //旧的和新的相比求出最新的
            dp[i]=Math.max(dp[i-1],dp[i-2]+value[i]);
        }
        return dp[value.length-1];

    }
public int Maxmoney(int[] value){
       if(value.length==0){
           return 0;
       }
       if(value.length==1){
           return value[0];
       }
       return Math.max(robAction(value,0,value.length-1),robAction(value,1,value.length));

}
public int robAction(int[]num,int start,int end){
      int x=0,y=0,z=0;
      for(int i=start;i<end;i++){
          y=z;
          z=Math.max(y,x+num[i]);
          x=y;
      }
      return z;

}




}
